"""
希尔排序，对列表跳跃选取建立排序子链，对各排序子链实现插入排序后再度细分划分指标
"""
def shell_Sort(target_List: list):
    gap = len(target_List) // 2  # 划分指标初始化,默认为列表一半长度
    while gap > 0:  # 划分小于1，整除情况下为0时结束
        j = gap  # 排序子链的尾元素位置记录为j
        while j < len(target_List):  # 排序链尾元素非法时所有元素排序完成
            index = j - gap  # index 初始化为当前排序子链中倒数第二元素位置
            while index >= 0:   # 直到当前排序链中所有值都插入排序完成
                if target_List[index + gap] > target_List[index]:
                    break  # 如果该序偶中后值大于前值 不执行操作
                else:  # 后值小，进行交换
                    target_List[index + gap], target_List[index] \
                        = target_List[index], target_List[index + gap]
                index -= gap  # 做完一轮判断后，index减去一个间隔指标，尝试对该链的前一序偶比较
            # 当前排序链排序完成，对下一排序链执行排序
            j += 1
        # print("当前划分完成：" + str(target_list) + "，划分指标gap= " + str(gap))
        gap //= 2  # 当前划分下排序完成，划分指标减半


# 示例
data = [16, 25, 39, 27, 12, 8, 45, 63]
shell_Sort(data)
print(data)
# 结果如下：
# # 当前划分完成：[12, 8, 39, 27, 16, 25, 45, 63]，划分指标gap= 4
# # 当前划分完成：[12, 8, 16, 25, 39, 27, 45, 63]，划分指标gap= 2
# # 当前划分完成：[8, 12, 16, 25, 27, 39, 45, 63]，划分指标gap= 1
# [8, 12, 16, 25, 27, 39, 45, 63]
